#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ORDER 4                  // B树的阶数
#define MIN_KEYS (ORDER - 1) / 2 // 最小关键字数

// B树结点结构
struct BTreeNode
{
    int keys[ORDER - 1];            // 关键字数组
    struct BTreeNode *child[ORDER]; // 子结点指针数组
    int numKeys;                    // 当前结点关键字数量
    bool isLeaf;                    // 是否为叶子结点
};

// 创建新结点
struct BTreeNode *createNode(bool isLeaf)
{
    struct BTreeNode *node = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
    node->numKeys = 0;
    node->isLeaf = isLeaf;

    // 初始化子结点指针为NULL
    for (int i = 0; i < ORDER; i++)
    {
        node->child[i] = NULL;
    }

    return node;
}

// 分裂子结点
void splitChild(struct BTreeNode *parent, int childIndex)
{
    struct BTreeNode *child = parent->child[childIndex];
    struct BTreeNode *newNode = createNode(child->isLeaf);

    // 新结点获取原结点后半部分的关键字
    newNode->numKeys = MIN_KEYS;
    for (int j = 0; j < MIN_KEYS; j++)
    {
        newNode->keys[j] = child->keys[j + ORDER / 2];
    }

    // 如果不是叶子结点，复制子结点指针
    if (!child->isLeaf)
    {
        for (int j = 0; j < ORDER / 2; j++)
        {
            newNode->child[j] = child->child[j + ORDER / 2];
        }
    }

    // 更新原结点的关键字数量
    child->numKeys = MIN_KEYS;

    // 在父结点中为新结点腾出位置
    for (int j = parent->numKeys; j > childIndex; j--)
    {
        parent->child[j + 1] = parent->child[j];
    }
    parent->child[childIndex + 1] = newNode;

    // 移动父结点的关键字
    for (int j = parent->numKeys - 1; j >= childIndex; j--)
    {
        parent->keys[j + 1] = parent->keys[j];
    }

    // 将中间关键字提升到父结点
    parent->keys[childIndex] = child->keys[MIN_KEYS];
    parent->numKeys++;
}

// 在未满结点中插入关键字
void insertNonFull(struct BTreeNode *node, int key)
{
    // 从最右侧开始查找插入位置
    int i = node->numKeys - 1;

    // 如果是叶子结点，直接插入
    if (node->isLeaf)
    {
        // 找到合适位置并移动大于key的关键字
        while (i >= 0 && key < node->keys[i])
        {
            node->keys[i + 1] = node->keys[i];
            i--;
        }

        // 插入新关键字
        node->keys[i + 1] = key;
        node->numKeys++;
    }
    else
    {
        // 找到合适的子结点
        while (i >= 0 && key < node->keys[i])
        {
            i--;
        }
        i++;

        // 如果子结点已满，先分裂
        if (node->child[i]->numKeys == ORDER - 1)
        {
            // 分裂子结点
            splitChild(node, i);

            // 确定新关键字应该插入哪个子结点
            if (key > node->keys[i])
            {
                i++;
            }
        }

        // 递归插入到子结点
        insertNonFull(node->child[i], key);
    }
}

// 插入关键字到B树
struct BTreeNode *insert(struct BTreeNode *root, int key)
{
    // 如果树为空
    if (root == NULL)
    {
        root = createNode(true);
        root->keys[0] = key;
        root->numKeys = 1;
        return root;
    }

    // 如果根结点已满，需要分裂
    if (root->numKeys == ORDER - 1)
    {
        struct BTreeNode *newRoot = createNode(false);
        newRoot->child[0] = root;
        splitChild(newRoot, 0);

        // 确定新关键字应该插入哪个子结点
        int i = 0;
        if (key > newRoot->keys[0])
        {
            i++;
        }

        insertNonFull(newRoot->child[i], key);
        return newRoot;
    }
    else
    {
        // 根结点未满，直接插入
        insertNonFull(root, key);
        return root;
    }
}

// 打印B树（中序遍历）
void printBTree(struct BTreeNode *root)
{
    if (root != NULL)
    {
        int i;
        for (i = 0; i < root->numKeys; i++)
        {
            // 递归打印左子树
            if (!root->isLeaf)
            {
                printBTree(root->child[i]);
            }
            // 打印当前关键字
            printf("%d ", root->keys[i]);
        }

        // 递归打印最后一个子树
        if (!root->isLeaf)
        {
            printBTree(root->child[i]);
        }
    }
}

// 主函数测试
int main()
{
    struct BTreeNode *root = NULL;

    // 测试插入序列
    int arr[] = {10, 20, 5, 6, 12, 30, 7, 17, 3, 1, 8, 25};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Inserting values: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
        root = insert(root, arr[i]);
    }
    printf("\n");

    // 打印B树（中序遍历）
    printf("Inorder traversal of the constructed B-tree: ");
    printBTree(root);
    printf("\n");

    return 0;
}